package com.cty.A_GeneralDataStructures.D_HashTable.OpenAddress;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/15 18:55
 * @Description: 再哈希法的开放地址法 哈希表
 * 应用场景：
 *      当数据量大时，考虑哈希表或树
 *          当数据量可预测且对查找、插入速度要求高时，考虑哈希表
 *              使用开放地址法时，对于小型哈希表，一般再哈希法效果最好
 * 重要操作：
 *      ① find(long): DataItem    O(1)
 *      ② insert(DataItem): void    O(1)
 *      ③ delete(long): DataItem    O(1)
 * @version: 1.0
 */
public class HashTable3 {
    private int maxSize;  // 为减少聚集，容量应为质数
    private DataItem[] array;
    private DataItem nonItem;

    public HashTable3(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nonItem = new DataItem(-1);
    }

    public void displayHashTable(){
        for(int i=0; i<maxSize; i++)
            if(array[i] != null)
                System.out.print(array[i] .getKey() + " ");
            else
                System.out.print("-- ");
        System.out.println();
    }

    private int hashFunc(long key){
        return (int)(key % maxSize);
    }

    private int hashFunc2(long key){  // 要求：与第一个哈希函数不同，步长不能为0
        return (int)(5 - key % 5);
    }

    /**
     * 线性查找  O(1) 聚集不严重时
     * @param key
     * @return
     */
    public DataItem find(long key){
        int hashValue = hashFunc(key);
        int hashStep = hashFunc2(key);

        while(array[hashValue] != null){  // 遇到空位结束
            if(array[hashValue].getKey() == key)  // 找到结束
                return array[hashValue];

            hashValue = (hashValue + hashStep) % maxSize;
        }  // end while
        return  null;
    }  // end find()

    /**
     * 线性插入  O(1) 聚集不严重时
     * @param item
     */
    public void insert(DataItem item){
        int hashValue = hashFunc(item.getKey());
        int hashStep = hashFunc2(item.getKey());

        while(array[hashValue]!=null && array[hashValue].getKey()!=-1){  // 遇到空位或标识删除位结束
            hashValue = (hashValue + hashStep) % maxSize;
        }  // end while
        array[hashValue] = item;
    }  // end insert()

    /**
     * 线性删除  O(1) 聚集不严重时
     * @param key
     * @return
     */
    public DataItem delete(long key){
        int hashValue = hashFunc(key);
        int hashStep = hashFunc2(key);

        while(array[hashValue] != null){  // 遇到空位结束
            if(array[hashValue].getKey() == key){
                DataItem temp = array[hashValue];
                array[hashValue] = nonItem;
                return temp;
            }
            hashValue = (hashValue + hashStep) % maxSize;
        }  // end while
        return null;
    }  // end delete()

}  // end HashTable3{}

/**
 * Enter size of hash table: 11
 * Enter initial number of items: 6
 * Enter first letter of show, insert, delete or find: s
 * -- -- 35 47 26 57 -- 62 27 -- --
 * Enter first letter of show, insert, delete or find: i
 * Enter key value to insert: 12
 * Enter first letter of show, insert, delete or find: s
 * -- 12 35 47 26 57 -- 62 27 -- --
 * Enter first letter of show, insert, delete or find: f
 * Enter key value to find: 57
 * Found 57
 * Enter first letter of show, insert, delete or find: d
 * Enter key value to delete: 47
 * Enter first letter of show, insert, delete or find: s
 * -- 12 35 -1 26 57 -- 62 27 -- --
 * Enter first letter of show, insert, delete or find: i
 * Enter key value to insert: 14
 * Enter first letter of show, insert, delete or find: s
 * -- 12 35 14 26 57 -- 62 27 -- --
 */
